package indi.caspar.algorithms;

import java.util.Random;
import java.util.jar.Pack200;

/**
 * Created by casparhuan on 2017/3/1.
 */
public class Sorts {

    public static void main(String[] args) {
        Sorts sorts = new Sorts();
        SortUtil<Integer> sortUtil = new SortUtil<Integer>();
        int[] data = {1,5,1,2,4,3,6,8,9,45,21,3,8,0,54,6,5,0,0,0,2,4,6,2};
        sorts.print(data);
        sorts.print(sorts.mergeSort(data,0,data.length-1));
    }

    //归并排序-归
    public int[] mergeSort(final int[] data,int lo,int hi){
        if(hi<=lo) return data;
        int middle = lo + (hi-lo)/2;
        mergeSort(data,lo,middle);
        mergeSort(data,middle+1,hi);
//        merge(data,lo,middle,hi);//第一种
        merge2(data,lo,middle,hi);//第二种
        return data;
    }

    //归并排序-并 第二种
    private void merge2(final int[] data,int lo ,int middle,int hi){
        int[] left =new int[middle - lo + 1 ];
        int[] right = new int[hi - middle];
        for (int i = 0 , j=0; i < left.length; i++,j++)
            left[i] = data[lo+j];
        for (int i = 0 , j=1; i < right.length ; i++,j++)
            right[i] = data[middle+j];

        for (int i = lo,j=0,k=0 ; i <= hi ; i++) {
            if (j>=left.length)
                data[i] = right[k++];
            else if (k >= right.length)
                data[i] = left[j++];
            else if (left[j] > right[k])
                data[i] = right[k++];
            else
                data[i] = left[j++];
        }

    }


    //归并排序-并
    private void merge(final int[] data, int lo, int middle, int hi) {
        int[] aux = new int[hi-lo +1];
        for (int k = lo,h=0; k <= hi ; k++) {
            aux[h++] = data[k];
        }
        int i = 0 , j = middle -lo +1;
        for (int k = lo; k <= hi ; k++) {
            if (i > middle -lo)
                data[k] = aux[j++];
            else if (j > aux.length-1)
                data[k] = aux[i++];
            else if (aux[i] > aux[j])
                data[k] = aux[j++];
            else
                data[k] = aux[i++];
        }

    }


    //交换排序
    //冒泡排序
    public int[] bubbleSort(final int[] data){
        for (int i = 0; i < data.length; i++) {
            for (int j = 1; j < data.length - i ; j++) {
                if (data[j-1] > data[j]){
                    //交换
                    int temp = data[j - 1];
                    data[j - 1] = data[j];
                    data[j] = temp;
                }
            }
        }
        return data;
    }

    //快速排序
    public int[] quickSort(final int[] data){
        return quickSort(data,0,data.length - 1);
    }

    public int[] quickSort(final int[] data,int low,int hight){
        if (hight > low) {
            int pivotLoc = partition(data, low, hight);
            quickSort(data,low,pivotLoc-1);
            quickSort(data,pivotLoc + 1 ,hight);
        }
        return data;
    }

    //随机找一个数当作中间数，分成左右两半。左边的小于中间数，右边大于中间数
    private int partition(int[] data, int low, int hight) {
        int privotKey = data[low];
        while ( low  < hight ) {
            while (low < hight && data[hight] >= privotKey) hight--;
            data[low] = data[hight];
            while (low < hight && data[low] <= privotKey) low++;
            data[hight] = data[low];
        }
        data[low] = privotKey;
        return low;
    }


    //插入排序
    //希尔排序
    public int[] shellSort(final int[] data){
        int dk = data.length /2;
        int round =0;//记录多少轮循环
        while (dk>=1){
            round++;
            //简单插入排序
            for (int i = dk; i < data.length ; i++) {
                if (i-dk >= 0 && data[i] < data[i-dk] ){
                    int temp = data[i];
                    data[i] = data[i - dk];
                    int j = i - dk;
                    while ((j-dk) >=0 && temp <  data[j-dk]){
                        data[j] = data[j-dk];
                        j -= dk;
                    }
                    data[j] = temp;
                }
            }
            System.out.print("No."+round + "轮循环，dk为"+dk+"，排序后为：");
            print(data);
            dk = dk/2;
        }
        return data;
    }

    //简单插入排序
    public int[] simpleInsertionSort(final int[] data){
        for (int i = 1; i < data.length ; i++) {
            if (data[i] < data[i-1]){
                int temp = data[i];
                data[i] = data[i-1];
                int j = i-1;
                while (j >=0 && temp < data[j] ){
                    data[j+1] = data[j];
                    j--;
                }
                data[j+1] = temp;
                System.out.print("No."+(i-1) +" round: ");
                print(data);
            }

        }
        return data;
    }

    public void print(int[] data){
        for (int i = 0; i < data.length; i++) {
            System.out.print(data[i] + " ");
        }
        System.out.println();
    }

}
